package test.n00500;


import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;

import static utils.Tools.listOf;

public class Problem00560 {
    public static void main(String[] args) {
        println(new int[][]{
                {1, 3}, {2, 6}, {8, 10}, {15, 18}
        });
        println(new int[][]{
                {1, 4}, {4, 5}
        });
        println(new int[][]{
                {1, 4}, {0, 4}
        });
        println(new int[][]{
                {2, 3}, {4, 5}, {6, 7}, {8, 9}, {1, 10}
        });
    }

    public static void println(int[][] matrix) {
        Solution ss = new Solution();
        System.out.println(listOf(matrix) + "," + ss.merge(matrix));
    }

    public static class Solution {

        /**
         * 以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。
         * <p>
         * 来源：力扣（LeetCode）
         * 链接：https://leetcode.cn/problems/merge-intervals
         * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
         *
         * @param intervals
         * @return
         */
        public int[][] merge(int[][] intervals) {
            List<List<Integer>> result = new ArrayList<>();

            if (intervals.length <= 1) {
                return intervals;
            }
            Arrays.sort(intervals, Comparator.comparingInt(array -> array[0]));
            result.add(Arrays.asList(intervals[0][0], intervals[0][1]));

            for (int i = 1; i < intervals.length; i++) {
                if (checkMerge(result, intervals[i])) {
                    merge(result, intervals[i]);
                } else {
                    result.add(Arrays.asList(intervals[i][0], intervals[i][1]));
                }
            }

            int[][] array = new int[result.size()][2];
            for (int i = 0; i < result.size(); i++) {
                array[i][0] = result.get(i).get(0);
                array[i][1] = result.get(i).get(1);
            }
            return array;
        }

        private boolean checkMerge(List<List<Integer>> result, int[] array2) {
            List<Integer> lastItem = result.get(result.size() - 1);
            if (lastItem.get(1) < array2[0]) {
                return false;
            }
            return true;
        }

        private void merge(List<List<Integer>> result, int[] array2) {
            List<Integer> lastItem = result.get(result.size() - 1);
            if (lastItem.get(1) >= array2[0]) {
                lastItem.set(0, lastItem.get(0) > array2[0] ? array2[0] : lastItem.get(0));
                lastItem.set(1, lastItem.get(1) > array2[1] ? lastItem.get(1) : array2[1]);
            } else {
                result.add(Arrays.asList(array2[0], array2[1]));
            }
        }

    }
}
